The present invention relates to a technique of rearranging packets in an apparatus that receives packets, in particular packets transmitted by a transmission path in which an order of transmission is not guaranteed.
In recent years, due to the development of application software (hereinafter may be simply referred to as an “application”) such as WWW (World Wide Web), IP (Internet Protocol)-based packet communication has become popular.
Since the transfer paths of the packets are not necessarily fixed in the IP-based packet communication, the arrival order of the packets at the receiving apparatus does not necessarily match the order of transmission due to congestion or the like. In the application that processes received packets, packets received in an order different from the order of transmission cannot be normally received.
Accordingly, such an operation is performed in which a transmission apparatus adds a sequence number according to an order of transmission to each of the packets to be transmitted, and the receiving apparatus rearranges the received packets in an order of the sequence numbers to pass the packets to the application.
It is known that a CPU (Central Processing Unit) performs rearrangement of the packets in the receiving apparatus. However, according to the recent spread of various types of network apparatuses, processing of the application has been more and more diversified. Further, according to the improvement in the high-speed communication infrastructure represented by an optical fiber communication network, high-speed processing is required in the side of the receiving apparatus.
Under such circumstances, performance of rearrangement of packets by the CPU causes interruption to the CPU every time the packet is received. This puts an enormous burden on the CPU which performs control of the whole receiving apparatus in addition to the processing of the application, resulting in the poor efficiency of the whole receiving apparatus.
In order to overcome such problems, various techniques have been proposed to achieve rearrangement of packets by hardware in place of the CPU.
FIG. 29 corresponds to FIG. 9 of Japanese Unexamined Patent Application Publication No. 2001-111608 with different reference symbols, and shows an interface on a side of a receiving apparatus to which the technique in this literature is applied. With reference to FIG. 29, a packet rearrangement technique disclosed in Japanese Unexamined Patent Application Publication No. 2001-111608 will be described.
An interface shown in FIG. 29 includes a rearrangement controller 1 and a rearrangement buffer 4. The rearrangement controller 1 includes a sequence number separation unit 2 and a ring counter for reading pointer 3.
In the rearrangement controller 1, the sequence number separation unit 2 separates the sequence number from a header of the packet that is received, to generate a writing pointer indicating the position in the rearrangement buffer 4 where the packet is written. The ring counter for reading pointer 3 generates a reading pointer indicating the position where the packet is read out for the rearrangement buffer 4. In the rearrangement buffer 4, packet data is written by a writing unit (not shown) in the position indicated by the writing pointer in a writing operation. Further, the rearrangement buffer 4 outputs packet data stored in the position indicated by the reading pointer by a reading unit (not shown) in a reading operation.
The numbers in the rearrangement buffer 4 indicate the addresses that store the packet data, and correspond to the values of the writing pointer and the reading pointer. The storage area of each address in the rearrangement buffer 4 includes an area to store the packet data and an area to store a store flag indicating whether the packet data is stored in the area.
The sequence number separation unit 2 in the rearrangement controller 1 generates the writing pointer in the order of the sequence numbers of the packets that are received, and a writing unit (not shown) writes the packet data in the address indicated by the writing pointer generated by the sequence number separation unit 2 and displays the store flag of the address.
In the reading operation, the reading unit generates a reading pointer using the ring counter for reading pointer 3, to search the store flag held in the area of the rearrangement buffer 4 indicated by the pointer. At this time, if the store flag is in an indication state, this means that packets are stored. Thus, the reading unit reads and outputs the packet data that is stored in the area. At the same time, the reading unit sets the store flag to non-indication and advances the count value of the ring counter for reading pointer 3 by one to search the storage area of the next packet. In this way, the packets are rearranged in the order of the sequence numbers or the order of transmission and are read out.
When the reading is performed when the state of the rearrangement buffer 4 is as shown in FIG. 30 (FIG. 10 in Japanese Unexamined Patent Application Publication No. 2001-111608), the packets are read out to the address number of 155. However, the packet which should be written in the address number 156, i.e., the packets written in the address number 155 and the address number 157 have not been arrived, whereby the reading unit continues to search the store flag and the reading operation is stopped.
In this case, the technique disclosed in Japanese Unexamined Patent Application Publication No. 2001-111608 measures time during which reading is stopped. When the measured time reaches a threshold, it is determined that the packet to be written in the address number 156 is lost. Then, the ring counter for reading pointer 3 is forcibly incremented by one, and the store flag of the address indicated by the reading pointer after the increment is checked and the packet data is read out.
FIG. 31 corresponds to FIG. 1 of Japanese Unexamined Patent Application Publication No. 2001-189755 with different reference symbols, and shows a communication system to which the technique in this literature is applied. With reference to FIG. 31, a packet rearrangement technique disclosed in Japanese Unexamined Patent Application Publication No. 2001-189755 will be described. Since a communication apparatus 10 and a communication apparatus 20 have the similar configurations in the system shown in FIG. 31, the illustration and description of each functional block of the communication apparatus 10 will be omitted. Further, for the communication apparatus 20, only functional blocks related to the packet rearrangement at the time of reception will be described in detail.
The communication apparatus 20 includes a packetizer circuit 21, a counter 22, a packet transmitting/receiving circuit 23, a packet assembler circuit 24, a reception buffer 25, a timer 26, a list 27, and an order rearranging unit 28. Among these functional blocks, the packet transmitting/receiving circuit 23, the packet assembler circuit 24, the reception buffer 25, the timer 26, the list 27, and the order rearranging unit 28 are related to packet rearrangement.
The packet transmitting/receiving circuit 23 receives packets from the communication apparatus 10 by way of a communication network 30 to pass the packets to the packet assembler circuit 24. The sequence numbers added by the communication apparatus 10 according to the order of transmission are added to headers of the received packets.
The packet assembler circuit 24 passes a sequence number Sc and the data of the packet from the packet transmitting/receiving circuit 23 to the order rearranging unit 28.
The reception buffer 25 is a buffer to allow data of packets to be output in the order in which they were transmitted. The application or the like retrieves data from the reception buffer 25 to achieve various processing. Further, the reception buffer 25 also stores a sequence number Sb of the packet which is transmitted last among the packets that have already been arrived.
The list 27 is a list (waiting list) which includes the sequence numbers of the packets that are expected to be arrived. The order rearranging unit 28 performs control of each functional block, rearrangement of packets, registration of the packets that are expected to arrive at the list 27 and the like described above.
FIGS. 32 and 33 correspond to flowcharts shown in FIGS. 2 and 3 of Japanese Unexamined Patent Application Publication No. 2001-189755 with different step numbers. Referring to FIGS. 32 and 33, processing of the order rearranging unit 28 will be described.
Upon receiving the packet data and a sequence number Sc from the packet assembler circuit 24, the order rearranging unit 28 compares the sequence number Sc with the sequence number Sb (sequence number of the packet which is transmitted last among the packets that have already been arrived) stored in the reception buffer 25 (S11, S13, and S15).
When Sc=Sb (S11: Y) as a result of the comparison, the order rearranging unit 28 determines that the newly received packet (packet of the sequence number Sc) is a repeated packet, and deletes (discards) the data from the reception buffer 25 (S12).
Further, when Sc=Sb+1 (S11: N, S13: Y), the order rearranging unit 28 regards the packet of the sequence number Sc and the packet of the sequence number Sb as consecutive packets and stores the packet of the sequence number Sc in the area next to the area in the reception buffer 25 in which the packet of the sequence number Sb is stored (S14).
Furthermore, when Sc<Sb (S11: N, S13: N, S15: Y), the order rearranging unit 28 searches the sequence number Sc from the list (S16).
When there is no sequence number Sc in the list 27 (S16: N), the order rearranging unit 28 discards the packet of the sequence number Sc (S17).
Further, when the sequence number Sc is hit in the list 27 (S16: Y) as a result of searching the list 27, the order rearranging unit 28 deletes the corresponding sequence number from the list 27 (S18), cancels (stops) the counting operation of the timer 26 that corresponds to the corresponding sequence number (S19), and inputs the data of the corresponding packet to a suitable position of the reception buffer 25 corresponding to the sequence number Sc (S20).
On the contrary, when Sc<Sb is not satisfied (S15: N) as a result of the comparison in Step S15, i.e., Sc>(Sb+1) is satisfied, the order rearranging unit 28 stores the packet of the sequence number Sc in the reception buffer 25 (S21). At the same time, in order to wait for the packets having the sequence numbers of Sb+2−Sc−1, the order rearranging unit 28 adds these sequence numbers to the list 27 of waiting packets (S22), to start the counting operation of the timer 26 for each of the sequence numbers of the waiting packets (S23). While the description of Step S22 (paragraph “0047”) in the specification of Japanese Unexamined Patent Application Publication No. 2001-189755 states that the sequence numbers of “Sb+1−Sc−1” are added to the list 27, the sequence numbers are changed to “Sb+2−Sc−1” in this specification as shown in the flowchart in FIG. 32.
FIG. 33 shows processing of the order rearranging unit 28 when the timer 26 times out. After a predetermined period of time has elapsed after the order rearranging unit 28 starts the counting operation of the timer 26 and the timer 26 times out (S31), the order rearranging unit 28 searches the sequence number associated with the timer 26 from the list 27 (S32).
When the corresponding sequence number was found as a result of the search (S32: Y), the order rearranging unit 28 deletes the sequence number from the list 27 (S33), treats the corresponding packet as a missing packet, and ends the processing.
When the corresponding sequence number was not found as a result of the search (S32: N), the order rearranging unit 28 ends the processing.
According to the technique disclosed in Japanese Unexamined Patent Application Publication No. 2001-189755, it is possible to rearrange the packets in the order of transmission in the receiving side even when the order of reception is different from the order of transmission.
In communication apparatuses compliant with IEEE802.3 standard, communication protocols such as TCP/IP (Transmission Control Protocol/Internet Protocol), UDP/IP (User Datagram Protocol/Internet Protocol) and the like are used.
For example, in the case of the TCP/IP, while sequence numbers of packets become larger as the order of transmission becomes later, these values are not incremented by one according to the order of transmission. This will be described with reference to FIGS. 34-36 with the configuration of the TCP/IP packet.
FIG. 34 shows a format of a TCP/IP packet. As shown in FIG. 34, a TCP/IP packet 50 includes an IP header 60, a TCP header 70, and a payload 90 which is application data.
The IP header 60 is located in a network layer of an OSI (Open System Interconnection) reference model, and includes information for addressing an apparatus connected to the network and selecting a communication path in a plurality of networks connected to one another.
As shown in FIG. 35, the IP header 60 includes IP packet information 61 indicating the information such as a packet length, a transmission source IP address 62, and a destination IP address 63.
The TCP header 70 is located in a transport layer of the OSI reference model, and includes information regarding to which processing the payload 90 to be transferred should be passed.
As shown in FIG. 36, the TCP header 70 includes a transmission source port number 71 to identify a program of a transmission source, a destination port number 72 to identify a destination program, a sequence number 73 indicating the order of transmission, an acknowledgment number 74 indicating the sequence number to be received next, an offset 75 indicating the TCP header length, a reserved field 76 for future extension, a TCP flag 77 indicating the control bit, a window 78 indicating the size of the data that can be received in the receiving side, a checksum 79 indicating the checksum of the payload 90, and an urgent point 80 indicating the position where time-critical data is stored.
The initial value of the sequence number 73 (sequence number of the first packet) is determined by a random number when the connection between transmission apparatuses is established. After that, the sequence number which is a sum of the sequence number 73 of the packet that is immediately previously transmitted and the payload length is given to the packet that is currently transmitted. The payload length is a data length of the payload 90 of the TCP header 70 of the packet.
The acknowledgement number 74 is a sum of the sequence number 73 and the payload length. In summary, the acknowledgement number 74 is the sequence number of the packet which is to be transmitted next. When the sequence number 73 of the currently-received packet matches the acknowledgment number 74 of the immediately-previously-received packet, the currently-received packet and the immediately-previously-received packet are consecutive packets.
The transmission apparatus of the TCP/IP packet generates packets having the configurations shown in FIGS. 34-36 to transmit the packets in the transmission processing. If the packet received in the receiving side is a packet transmitted after being divided (hereinafter also referred to as a “divided packet”), the TCP header of the packet includes the sequence number 73 of the packet.
In the TCP protocol, the maximum length MSS (Maximum Segment Size) of the payload 90 is determined, and the application data is transmitted after being divided into the size of MSS or smaller.
The window 78 in the TCP header 70 indicates the size of the buffer of the transmission destination. The transmission apparatus is able to continuously transmit packets until when the number of pieces of data transmitted after being divided into the size of MSS and smaller becomes equal to the window size indicated by the window 78. When the number reaches the window size, the transmission apparatus temporarily stops transmitting the packets, and start transmission of the packets again after detecting the reception response from the receiving side.
As will be understood from the description above, in the case of the TCP/IP, the sequence number becomes larger as the order of transmission becomes later. However, the sequence number is not incremented by one according to the order of transmission. Further, since the payload length is not a fixed value although the maximum length MSS of the payload is determined, the increment value of the sequence number is not a fixed value.